package day03;

/**
 * @author Jetwang
 * @version 1.0
 * @since 2023/3/13 13:32
 * Offer 14- I. 剪绳子
 */
public class Offer14B {
    public int cuttingRope(int n) {
        if (n <= 2) {
            return 1;
        }
        if (n == 3) {
            return 2;
        }

        int res = n / 3;
        int mod = n % 3;
        int p = 1000000007;

        if (mod == 0) {
            return (int)pow(3, res);
        } else if (mod == 1) {
            return (int) ((pow(3, res - 1) * 4) % p);
        } else {
            return (int) ((pow(3, res) * mod) % p);
        }
    }

    long pow(int a, int n) {
        long res = 1;
        int p = 1000000007;
        for (int i = 1; i <= n; i++) {
            res = (res * a) % p;
        }
        return res;
    }
}
